package indexof

func DFA(pat []rune) (dfa [][]int) {

	runes := pat
	patlen := len(runes)

	for i := 0; i < 256; i++ {
		tmp := make([]int, patlen)
		dfa = append(dfa, tmp)
	}

	dfa[runes[0]][0] = 1

	for x, j := 0, 1; j < patlen; j++ {

		for c := 0; c < 256 && x < patlen; c++ {
			dfa[c][j] = dfa[c][x]
			dfa[runes[j]][j] = j + 1
			x = dfa[runes[j]][x]
		}
	}

	return dfa
}

func IndexOf(main, pat string) int{

	mains := [] rune(main)

	pats := [] rune(pat)

	dfa := DFA(pats)

	mainlen, patlen := len(mains), len(pats)
	i,j := 0,0
	for ; i < mainlen && j <patlen; i++ {

		j = dfa[mains[i]][j]
	}

	if j == patlen {
		return i - patlen
	}
		return -1
}
